import java.util.*;

/**
 * @Author Fizz Pu
 * @Date 2020/9/16 下午10:08
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */

// bfs问题,但是有一个问题,如何保存结果,这个不会处理
// 看了一些博客,没看懂
// 想到了一种类似于静态链表的实现


public class Maze{
    public static void main(String[] args) {
        int[][] maze = new int[][]{
                {0, 1, 0, 0, 0},
                {0, 1, 0, 1, 0},
                {0, 0, 0, 0, 0},
                {0, 1, 1, 1, 0},
                {0, 0, 0, 1, 0}
        };
        new Maze().getPath(maze);
    }


    public void getPath(int[][] maze){
        int maxRow = maze.length, maxCol = maze.length;
        Deque<Ele> queue = new LinkedList<>();
        queue.add(new Ele(0,0,-1)); //有点像并查集的原理
        List<Ele> path = new ArrayList<>();
        int index = -1; // ele在path中的下标

        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0; i < size; ++i){
                Ele ele = queue.remove();
                path.add(ele);
                ++index;
                int row = ele.getRow();
                int col = ele.getCol();

                if(row == maxRow-1 && col == maxCol-1){ // 找到出口
                    Deque<String> stack = new LinkedList<>();
                    while(ele.getFatherIndex() != -1){
                            stack.push("("+ele.getRow() + "," +ele.getCol()+")");
                            ele = path.get(ele.getFatherIndex());
                        }stack.push("(0,0)");
                    while (!stack.isEmpty()){
                        System.out.println(stack.remove());
                    }
                    return;
                }

                // 上下左右走
                if(row + 1 < maxRow && maze[row+1][col]==0){
                    queue.add(new Ele(row+1, col,index));
                    maze[row+1][col] = 1; // 避免重复遍历
                }if  (row - 1 >= 0 && maze[row-1][col]==0){
                    queue.add(new Ele(row-1, col, index));
                    maze[row-1][col] = 1; // 避免重复遍历
                }if (col + 1 < maxCol && maze[row][col+1]==0){
                    queue.add(new Ele(row, col+1, index));
                    maze[row][col+1] = 1; // 避免重复遍历
                }if(col -1 >=  0 && maze[row][col-1]==0){
                    queue.add(new Ele(row, col-1, index));
                    maze[row][col-1] = 1; // 避免重复遍历
                }
            }
        }
    }
}

class Ele{
    private final int row;
    private final int col;
    private final int fatherIndex; // 父节点所在的节点下标

    public Ele(int row, int col, int fatherIndex) {
        this.row = row;
        this.col = col;
        this.fatherIndex = fatherIndex;
    }

    public int getRow() {
        return row;
    }

    public int getCol() {
        return col;
    }

    public int getFatherIndex() {
        return fatherIndex;
    }
}